Wang Haihua
🍈 🍉🍊 🍋 🍌
树是图论中的基本概念。连通的无圈图称为树(Tree),就是不包含循环的回路的连通图。
对于无向连通图,如下图所示,生成树(Spanning tree)是原图的极小连通子图,它包含原图中的所有 n 个顶点,并且有保持图连通的最少的边,即只有足以构成一棵树的 n-1 条边。
生成树满足:
对于非连通无向图, 遍历每个连通分量中的顶点集合所经过的边是多颗生成树,这些连通分量的生成树构成非连通图的生成森林 。
遍历连通图的方式通常有很多种,也就是说一张连通图可能有多种不同的生成树。
无向赋权图的生成树中,各条边的权重之和最小的生成树,称为最小生成树(minimum spanning tree,MST),也称最小权重生成树。
对应地,各条边的权重之和最大的生成树,称为最大生成树(maximum spanning tree)。
最小生成树(MST)是图论中的基本问题,具有广泛的实际应用,在数学建模中也经常出现。
例如,在若干城市之间铺设通信线路,使任意两个城市之间都可以通信,要使铺设线路的总费用最低,就需要找到最小生成树。类似地,路线设计、道路规划、官网布局、公交路线、网络设计,都可以转化为最小生成树问题,如要求总线路长度最短、材料最少、成本最低、耗时最小等。
在实际应用中,不仅要考虑网络连通,还要考虑连通网络的质量和效率,就形成了带有约束条件的最小生成树:
直径限制最小生成树(Bounded diameter minimum spanning tree):对给定的连通图,满足直径限制的生成树中,具有最小权的树,称为直径限制最小生成树。直径限制最小生成树问题在资源优化问题中应用广泛,如网络设计的网络直径影响到网络的传输速度、效率和能耗。
度限制最小生成树(Degree constrained minimum spanning tree):对给定的连通图,满足某个节点或全部节点的度约束(如入度不超过 k)的生成树中,具有最小权的树,称为度限制最小生成树。实际应用中,为了控制节点故障对整个系统的影响,需要对节点的度进行限制。
构造最小生成树的算法很多,通常是从空树开始,按照贪心法逐步选择并加入 n-1 条安全边(不产生回路),最终得到最小生成树。
最小生成树的典型算法有普里姆算法(Prim算法)和克鲁斯卡算法(Kruskal算法)。
Prim 算法以顶点为基础构造最小生成树,每个顶点只与连通图连接一次,因此不用考虑在加入顶点的过程中是否会形成回路。
算法从某一个顶点 s 开始,每次选择剩余的代价最小的边所对应的顶点,加入到最小生成树的顶点集合中,逐步扩充直到包含整个连通网的所有顶点,可以称为“加点法”。
Prim 算法中图的存贮结构采用邻接矩阵,使用一个顶点集合 u 构造最小生成树。由于不断向集合u中加点,还需要建立一个辅助数组来同步更新最小代价边的信息。
Prim 算法每次选择顶点时,都需要进行排序,但每次都只需要对一部分边进行排序。Prim 算法的时间复杂度为 O(n*n),与边的数量无关,适用于边很多的稠密图。
Kruskal 算法以边为基础构造最小生成树,利用避圈思想,每次找到不使图构成回路的代价最小的边。
算法初始边数为 0,每次选择一条满足条件的最小代价边,加入到边集合中,逐步扩充直到包含整个生成树,可以称为“加边法”。
Kruskal 算法中图的存贮结构采用边集数组,权值相等的边在数组中的排列次序是任意的。Kruskal算法开始就要对所有的边进行排序,之后还需要对所有边应用 Union-Find算法,但不再需要排序。
Kruskal 算法的时间复杂度为 O(mlogm),主要是对边排序的时间复杂度,适用于边较少的稀疏图。
某市区有 7个小区需要铺设天然气管道,各小区的位置及可能的管道路线、费用如图所示,要求设计一个管道铺设路线,使天然气能输送到各个小区,且铺设管道的总费用最小。 其中数值0代表无管道连接,非零代表建设费用。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 5 | 6 | 0 | 0 | 0 | 0 | 0 | 9 | 0 |
1 | 5 | 0 | 1 | 2 | 12 | 0 | 5 | 0 | 0 | 2 |
2 | 6 | 1 | 0 | 6 | 0 | 7 | 0 | 0 | 0 | 0 |
3 | 0 | 2 | 6 | 0 | 8 | 0 | 4 | 0 | 0 | 3 |
4 | 0 | 12 | 0 | 8 | 0 | 0 | 0 | 1 | 0 | 0 |
5 | 0 | 0 | 7 | 0 | 0 | 0 | 5 | 0 | 7 | 0 |
6 | 0 | 5 | 0 | 4 | 0 | 5 | 0 | 10 | 0 | 0 |
7 | 0 | 0 | 0 | 0 | 1 | 0 | 10 | 0 | 0 | 0 |
8 | 9 | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 |
9 | 0 | 2 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
利用NetworkX种的克鲁斯卡算法,计算出最小生成树为:
import numpy as np
import matplotlib.pyplot as plt # 导入 Matplotlib 工具包
import networkx as nx # 导入 NetworkX 工具包
import pandas as pd
B=np.array([[ 0, 5, 6, 0, 0, 0, 0, 0, 9, 0],
[ 5, 0, 1, 2, 12, 0, 5, 0, 0, 2],
[ 6, 1, 0, 6, 0, 7, 0, 0, 0, 0],
[ 0, 2, 6, 0, 8, 0, 4, 0, 0, 3],
[ 0, 12, 0, 8, 0, 0, 0, 1, 0, 0],
[ 0, 0, 7, 0, 0, 0, 5, 0, 7, 0],
[ 0, 5, 0, 4, 0, 5, 0, 10, 0, 0],
[ 0, 0, 0, 0, 1, 0, 10, 0, 0, 0],
[ 9, 0, 0, 0, 0, 7, 0, 0, 0, 0],
[ 0, 2, 0, 3, 0, 0, 0, 0, 0, 0]])
B = pd.DataFrame(B)
print(B.to_markdown())
| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |---:|----:|----:|----:|----:|----:|----:|----:|----:|----:|----:| | 0 | 0 | 5 | 6 | 0 | 0 | 0 | 0 | 0 | 9 | 0 | | 1 | 5 | 0 | 1 | 2 | 12 | 0 | 5 | 0 | 0 | 2 | | 2 | 6 | 1 | 0 | 6 | 0 | 7 | 0 | 0 | 0 | 0 | | 3 | 0 | 2 | 6 | 0 | 8 | 0 | 4 | 0 | 0 | 3 | | 4 | 0 | 12 | 0 | 8 | 0 | 0 | 0 | 1 | 0 | 0 | | 5 | 0 | 0 | 7 | 0 | 0 | 0 | 5 | 0 | 7 | 0 | | 6 | 0 | 5 | 0 | 4 | 0 | 5 | 0 | 10 | 0 | 0 | | 7 | 0 | 0 | 0 | 0 | 1 | 0 | 10 | 0 | 0 | 0 | | 8 | 9 | 0 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | 0 | | 9 | 0 | 2 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
G = nx.from_pandas_adjacency(B)
T = nx.minimum_spanning_tree(G) # 返回包括最小生成树的图
print(T.nodes) # 最小生成树的 顶点
print(T.edges) # 最小生成树的 边
print(sorted(T.edges)) # 排序后的 最小生成树的 边
print(sorted(T.edges(data=True))) # data=True 表示返回值包括边的权重
mst1 = nx.tree.minimum_spanning_edges(G, algorithm="kruskal") # 返回最小生成树的边
print(list(mst1)) # 最小生成树的 边
mst2 = nx.tree.minimum_spanning_edges(G, algorithm="prim",data=False) # data=False 表示返回值不带权
print(list(mst2))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [(0, 1), (1, 2), (1, 3), (1, 9), (3, 6), (3, 4), (4, 7), (5, 6), (5, 8)] [(0, 1), (1, 2), (1, 3), (1, 9), (3, 4), (3, 6), (4, 7), (5, 6), (5, 8)] [(0, 1, {'weight': 5}), (1, 2, {'weight': 1}), (1, 3, {'weight': 2}), (1, 9, {'weight': 2}), (3, 4, {'weight': 8}), (3, 6, {'weight': 4}), (4, 7, {'weight': 1}), (5, 6, {'weight': 5}), (5, 8, {'weight': 7})] [(1, 2, {'weight': 1}), (4, 7, {'weight': 1}), (1, 3, {'weight': 2}), (1, 9, {'weight': 2}), (3, 6, {'weight': 4}), (0, 1, {'weight': 5}), (5, 6, {'weight': 5}), (5, 8, {'weight': 7}), (3, 4, {'weight': 8})] [(0, 1), (1, 2), (1, 3), (1, 9), (3, 6), (6, 5), (5, 8), (3, 4), (4, 7)]
pos={0:(1,1),2:(3,1),3:(3,5),4:(5,1),5:(5,5),6:(7,1),7:(7,5),8:(9,1),9:(9,5),1:(1,5)} # 指定顶点位置
nx.draw(G, pos, with_labels=True, node_color='c', alpha=0.8) # 绘制无向图
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels, font_color='m') # 显示边的权值
nx.draw_networkx_edges(G,pos,edgelist=T.edges,edge_color='orange',width=4) # 设置指定边的颜色
plt.savefig('images/opt0701.png')
plt.show()